package gold.utils;

/**
 * 参考文档：https://www.jianshu.com/p/91f2c503e62f
 */
public class SegmentTreeNodeUtil {

    // 节点区间定义
    // [start, end] 代表节点的区间范围
    // max 是节点在(start,end)区间上的最大值
    // left , right 是当前节点区间划分之后的左右节点区间
//    线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 log(width)log(width)。更新某个元素的值，只需要更新 log(width)log(width) 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。
//
//    线段树的每个节点代表一个区间；
//    线段树具有唯一的根节点，代表的区间是整个统计范围，如 [1, N][1,N]；
//    线段树的每个叶子节点代表一个长度为 11 的元区间 [x, x][x,x]；
//    对于每个内部节点 [l, r][l,r]，它的左儿子是 [l, mid][l,mid]，右儿子是 [mid + 1, r][mid+1,r], 其中 mid = ⌊(l + r) / 2⌋mid=⌊(l+r)/2⌋ (即向下取整)。

    public class SegmentTreeNode {
        public int start, end, max, sum;
        public SegmentTreeNode left, right;

        public SegmentTreeNode(int start, int end, int max) {
            this.start = start;
            this.end = end;
            this.max = max;
            this.left = this.right = null;
        }

        public SegmentTreeNode(int start, int end, int max, int sum) {
            this.start = start;
            this.end = end;
            this.max = max;
            this.sum = sum;
            this.left = this.right = null;
        }
    }

    // 构造的代码及注释
    public SegmentTreeNode build(int[] A) {
        // write your code here
        return buildHelper(0, A.length - 1, A);
    }

    public SegmentTreeNode buildHelper(int left, int right, int[] A) {
        if (left > right) {
            return null;
        }
        SegmentTreeNode root = new SegmentTreeNode(left, right, A[left]); // 根据节点区间的左边界的序列值为节点赋初值
        if (left == right) {
            return root; // 如果左边界和右边界相等,节点左边界的序列值就是线段树节点的接节点值
        }
        int mid = (left + right) / 2; // 划分当前区间的左右区间
        root.left = buildHelper(left, mid, A);
        root.right = buildHelper(mid + 1, right, A);
        root.max = Math.max(root.left.max, root.right.max); // 根据节点区间的左右区间的节点值得到当前节点的节点值
        root.sum = root.left.sum + root.right.sum;
        return root;
    }

    // 单点更新的代码及注释
    public void update(SegmentTreeNode root, int index, int value) {
        // write your code here
        if (root.start == root.end && root.start == index) { // 找到被改动的叶子节点
            root.max = value; // 改变value值
            root.sum = value;
            return;
        }

        int mid = (root.start + root.end) / 2; // 将当前节点区间分割为2个区间的分割线
        if (index <= mid) { // 如果index在当前节点的左边
            update(root.left, index, value); // 递归操作
            root.max = Math.max(root.right.max, root.left.max); // 可能对当前节点的影响
            root.sum = root.right.sum + root.left.sum;
        } else {            // 如果index在当前节点的右边
            update(root.right, index, value); // 递归操作
            root.max = Math.max(root.left.max, root.right.max); // 可能对当前节点的影响
            root.sum = root.left.sum + root.left.sum;
        }
        return;
    }

    // 区间查询的代码及注释
    public int queryMax(SegmentTreeNode root, int start, int end) {
        if (start <= root.start && root.end <= end) {
            // 如果查询区间在当前节点的区间之内,直接输出结果
            return root.max;
        }
        int mid = (root.start + root.end) / 2; // 将当前节点区间分割为左右2个区间的分割线
        int ans = Integer.MIN_VALUE; // 给结果赋初值
        if (mid >= start) {   // 如果查询区间和左边节点区间有交集,则寻找查询区间在左边区间上的最大值
            ans = Math.max(ans, queryMax(root.left, start, end));
        }
        if (mid + 1 <= end) { // 如果查询区间和右边节点区间有交集,则寻找查询区间在右边区间上的最大值
            ans = Math.max(ans, queryMax(root.right, start, end));
        }
        return ans; // 返回查询结果
    }

    // 区间查询的代码及注释
    public int querySum(SegmentTreeNode root, int start, int end) {
        if (start <= root.start && root.end <= end) {
            // 如果查询区间在当前节点的区间之内,直接输出结果
            return root.sum;
        }

        int mid = (root.start + root.end) / 2; // 将当前节点区间分割为左右2个区间的分割线
        int intervalSum = 0; // 给结果赋初值
        if (mid >= start) {   // 如果查询区间和左边节点区间有交集,则寻找查询区间在左边区间上的sum
            intervalSum += querySum(root.left, start, end);
        }
        if (mid + 1 <= end) { // 如果查询区间和右边节点区间有交集,则寻找查询区间在右边区间上的最大值
            intervalSum += querySum(root.right, start, end);
        }
        return intervalSum; // 返回查询结果
    }

}
